#pragma once

#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
#include <utility>

class Solution
{
public:
    std::vector<int> findSubstringSorted(std::string s, const std::vector<std::string>& words)
    {
        auto ids = findSubstring(s, words);
        std::sort(ids.begin(), ids.end());
        return ids;
    }

    std::vector<int> findSubstring(std::string s, const std::vector<std::string>& words)
    {
        int word_len = words.front().size();
        int sentence_len = words.size() * word_len;

        std::unordered_map<std::string_view, int> word_count;
        for (const auto& w : words) {
            auto sv = std::string_view(w.data(), word_len);
            auto it = word_count.find(sv);
            if (it == word_count.cend())
                it = word_count.emplace(sv, 0).first;
            ++it->second;
        }

        std::vector<int> start_ids;
        for (auto it = s.cbegin(); it + sentence_len - 1 != s.cend(); ++it) {
            if (check(it, it + sentence_len, word_count, word_len))
                start_ids.push_back(std::distance(s.cbegin(), it));
        }
        return start_ids;
    }

private:
    template <typename InputIt>
    bool check(InputIt first, InputIt last, std::unordered_map<std::string_view, int> word_count, int word_len)
    {
        for (; first != last; first += word_len) {
            auto sv = std::string_view(&(*first), word_len);
            auto it = word_count.find(sv);
            if (it == word_count.cend() || it->second == 0)
                return false;
            --it->second;
        }
        return std::all_of(word_count.cbegin(), word_count.cend(), [](auto& wc) { return wc.second == 0; });
    }
};

class Solution2
{
public:
    std::vector<int> findSubstringSorted(std::string s, const std::vector<std::string>& words)
    {
        auto ids = findSubstring(s, words);
        std::sort(ids.begin(), ids.end());
        return ids;
    }

    std::vector<int> findSubstring(std::string s, const std::vector<std::string>& words)
    {
        int word_len = words.front().size();
        int sentence_len = words.size() * word_len;

        std::unordered_map<std::string_view, int> word_count;
        for (const auto& w : words) {
            auto sv = std::string_view(w.data(), word_len);
            auto it = word_count.find(sv);
            if (it == word_count.cend())
                it = word_count.emplace(sv, 0).first;
            ++it->second;
        }

        std::vector< std::pair<int, std::string_view> > sorted_ids;
        for (auto it = s.cbegin(); it + word_len - 1 != s.cend(); ++it) {
            auto sv = std::string_view(&(*it), word_len);
            if (word_count.count(sv))
                sorted_ids.emplace_back(std::distance(s.cbegin(), it), sv);
        }

        std::vector<int> start_ids;
        for (auto it = sorted_ids.cbegin(); it + words.size() - 1 != sorted_ids.end(); ++it) {
            int s_begin = it->first;
            int s_end = it->first + sentence_len;
            if (s_end <= (int)s.size()) {
                if (check(s.cbegin() + s_begin, s.cbegin() + s_end, word_count, word_len))
                    start_ids.push_back(it->first);
            }
        }
        return start_ids;
    }

private:
    template <typename InputIt>
    bool check(InputIt first, InputIt last, std::unordered_map<std::string_view, int> word_count, int word_len)
    {
        for (; first != last; first += word_len) {
            auto sv = std::string_view(&(*first), word_len);
            auto it = word_count.find(sv);
            if (it == word_count.cend() || it->second == 0)
                return false;
            --it->second;
        }
        return std::all_of(word_count.cbegin(), word_count.cend(), [](auto& wc) { return wc.second == 0; });
    }
};
